
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}

    Node(int _val) : val(_val), left(nullptr), right(nullptr), next(nullptr) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        Node* now = nullptr;
        Node* start = root;
        while (start != nullptr) {
            now = start;
            start = nullptr;
            while (now != nullptr) {
                Node* tmp = nullptr;
                if (now->left != nullptr && now->right != nullptr) {
                    now->left->next = now->right;
                    tmp = now->right;
                }
                else if (now->right != nullptr) {
                    tmp = now->right;
                }
                else if (now->left != nullptr) {
                    tmp = now->left;
                }
                if (start == nullptr) {
                    if (now->left != nullptr) {
                        start = now->left;
                    }
                    else if (now->right != nullptr) {
                        start = now->right;
                    }
                }
                if (tmp != nullptr) {
                    Node* ter = now->next;
                    while (ter != nullptr && ter->left == nullptr && ter->right == nullptr) {
                        ter = ter->next;
                    }
                    if (ter != nullptr) {
                        if (ter->left != nullptr) {
                            tmp->next = ter->left;
                        }
                        else {
                            tmp->next = ter->right;
                        }
                    }
                }
                now = now->next;
            }
        }
        return root;
    }
};